package com.leetcode.algorithm.y18.m06;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-cn.com
 * (done)201. 数字范围按位与
 * (done)136. 只出现一次的数字
 * (done)137. 只出现一次的数字 II
 * (done)78. 子集
 * (done)338. Bit位计数
 * @author: jie.deng
 * @time: 2018年6月6日 下午1:14:30
 */
public class MySolution0606 {
	/**
	 * 201. 数字范围按位与
     * 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
     * 
     * 示例 1: 
     * 输入: [5,7]
     * 输出: 4
     * 
     * 示例 2:
     * 输入: [0,1]
     * 输出: 0
	 * @param m
	 * @param n
	 * @return
	 */
	public int rangeBitwiseAnd(int m, int n) {
		int diff = n - m;
		int l = 0xffffffff;
		while (diff > 0) {
			diff = diff >> 1;
			l = l << 1;
		}
		return (n & m) & l;
	}
    
	/**
	 * 136. 只出现一次的数字 
	 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
	 * 
	 * 说明：
	 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
	 * 
	 * 示例 1:
	 * 输入: [2,2,1] 
	 * 输出: 1 
	 * 
	 * 示例 2:
	 * 输入: [4,1,2,1,2] 
	 * 输出: 4
	 * 
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		// 异或运算(同0异1)
		int number = 0;
		for (int i = 0; i < nums.length; i++) {
			number ^= nums[i];
		}
		return number;
	}
	
    /**
     * 137. 只出现一次的数字 II
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
     * 
     * 说明：
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     * 
     * 示例 1:
     * 输入: [2,2,3,2]
     * 输出: 3
     * 
     * 示例 2:
     * 输入: [0,1,0,1,0,1,99]
     * 输出: 99
     * @param nums
     * @return
     */
	public int singleNumberII(int[] nums) {
		int ret = 0;
		int len = nums.length;
		for (int i = 31; i >= 0; i--) {
			ret <<= 1;
			int w = 0;
			for (int j = 0; j < len; j++) {
				w += ((nums[j] >>> i) & 1);
			}
			ret |= w % 3;
		}
		return ret;
	}
    
    /**
     * 260. 只出现一次的数字 III
     * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
     * 示例 :
     * 输入: [1,2,1,3,2,5]
     * 输出: [3,5]
     * 注意：
     * 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
     * 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
     * @param nums
     * @return
     */
	public int[] singleNumberIII(int[] nums) {
		// 先异或
		int num = 0;
		for (int i = 0; i < nums.length; i++) {
			num ^= nums[i];
		}
		// 取出其中不同的位
		int idx = 0;
		int tmp = num;
		while ((tmp & 1) != 1) {
			idx++;
			tmp = tmp >>> 1;
		}
		//
		int num2 = 0;
		for (int i = 0; i < nums.length; i++) {
			if ((nums[i] >>> idx & 1) == 1) {
				num2 ^= nums[i];
			}
		}
		return new int[] { num2, num2 ^ num };
	}
    
    
    /**
     * 78. 子集
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     * 
     * 示例:
     * 输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     * ]
     * @param nums
     * @return
     */
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		int len = nums.length;
		int max = (int) Math.pow(2, len);
		for (int i = 0; i < max; i++) { 	// i从0到(2的len次方-1)
			List<Integer> subList = new ArrayList<Integer>();
			for (int j = 0; j < len; j++) {
				int k = i >>> j;
				if ((k & 1) == 1) { 	// i的二进制表示哪一位为1则加入到subList
					subList.add(nums[j]);
					continue;
				}
				if (k == 0) {
					break;
				}
			}
			list.add(subList);
		}
		return list;
	}
    
    
    /**
     * 338. Bit位计数
     * 给定一个非负整数 num。 对于范围 0 ≤ i ≤ num 中的每个数字 i ，计算其二进制数中的1的数目并将它们作为数组返回。
     * 
     * 示例：
     * 比如给定 num = 5 ，应该返回 [0,1,1,2,1,2].
     * 
     * 进阶：
     * 给出时间复杂度为O(n * sizeof(integer)) 的解答非常容易。 但是你可以在线性时间O(n)内用一次遍历做到吗？
     * 要求算法的空间复杂度为O(n)。
     * 你能进一步完善解法吗？ 在c ++或任何其他语言中不使用任何内置函数（如c++里的 __builtin_popcount）来执行此操作。
     * @param num
     * @return
     */
	public int[] countBits(int num) {
		int[] ret = new int[num + 1];
		ret[0] = 0;
		int pow = 1;
		while (pow <= num) {
			int begin = pow;
			pow = pow << 1;
			int end = Math.min(num + 1, pow);
			for (int i = begin; i < end; i++) {
				ret[i] = 1 + ret[i - begin];
			}
		}
		return ret;
	}
	public int[] countBitsSolution(int num) {
		int[] sum = new int[num + 1];
		for (int i = 1; i <= num; i++) {
			sum[i] = sum[i & i - 1] + 1;
		}
		return sum;
	}
}
